#include <iostream>
#include <vector>

typedef int ADT;

ADT BinarySearch(const std::vector<ADT> &array, ADT target)
{
    int left = 0;
    int right = array.size() - 1;
    while (left <= right)
    {
        int mid = (left + right) / 2;
        if (array[mid] == target)
            return mid;
        else if (array[mid] < target) // 目标右半部分
            left = mid + 1;
        else
            right = mid - 1; // 目标在左半部分
    }
    return -1;
}

int main()
{
    std::vector<ADT> array = {5, 9, 15, 18, 22, 25, 26, 38, 42, 45, 56, 56, 66, 69, 75, 78, 80, 83, 92, 99};

    int pos38 = BinarySearch(array, 38);
    std::cout << "38的位置: " << pos38 << std::endl;
    int pos5 = BinarySearch(array, 5);
    std::cout << "5的位置: " << pos5 << std::endl;
    int pos99 = BinarySearch(array, 99);
    std::cout << "99的位置: " << pos99 << std::endl;

    int pos388 = BinarySearch(array, 388);
    if (pos388 == -1)
        std::cout << "没有找到388" << std::endl;
    return 0;
}